// Copyright (c) 2011, the Dart project authors.  Please see the AUTHORS file
// for details. All rights reserved. Use of this source code is governed by a
// BSD-style license that can be found in the LICENSE file.

part of dart.core;

/**
 * 按顺序访问的值或元素的集合。
 *
 * 可迭代对象的元素通过[Iterator]来访问，该迭代器使用[iterator]的getter方法来获取，
 * 并且可使用迭代器对所有值进行单步遍历。
 * 迭代器通过调用[Iterator.moveNext]来进行遍历，
 * 如果调用返回`true`，迭代器会移动到下一个元素，并将元素作为[Iterator.current]可用的返回值。
 * 如果调用返回`false`，表示没有更多的元素，`iterator.current`返回`null`。
 *
 * 对于同一个`Iterable`，你可以创建多次迭代器。
 * 每次读取`iterator`，它会返回一个新的迭代器，
 * 不同的迭代器可以进行遍历而互不影响，每个迭代器都可以访问对象的所有元素。
 * 相同对象的迭代器*应该*提供相同的值和顺序（除非在迭代期间，基础集合被修改，部分集合允许此操作）。
 *
 * 泥也可以使用for-in循环结构来迭代`Iterable`的所有元素，
 * 该结构在后台同样使用了`iterator`的getter方法。
 * 例如，可以迭代[Map]所有的key值，因为`Map`的keys是可迭代对象。
 *
 *     Map kidsBooks = {'Matilda': 'Roald Dahl',
 *                      'Green Eggs and Ham': 'Dr Seuss',
 *                      'Where the Wild Things Are': 'Maurice Sendak'};
 *     for (var book in kidsBooks.keys) {
 *       print('$book was written by ${kidsBooks[book]}');
 *     }
 *
 * [List]和[Set]也是`Iterable`，[dart:collection](#dart-collection)库中同样有很多。
 *
 * 部分[Iterable]集合可以被修改。
 * 向`List`或`Set`添加元素将改变对象所有包含的元素。
 * 向`Map`添加新的Key会改变所有[Map.keys]的元素。
 * 在集合改变后，创建的迭代器将提供新的所有元素，
 * 并且可能会保持目前元素的顺序，也可能不会
 * （例如，在添加一个元素之后，[HashSet]也许会完全地改变它的顺序）。
 *
 * 迭代的*同时*修改集合，这通常是*不允许*的。这样做会破坏迭代。
 * 然后，通常会抛出[ConcurrentModificationError]，
 * 向下一次调用的[Iterator.moveNext]发出信号。
 * 当前[Iterator.current]的getter方法的值不应该受集合的变化影响，
 * `current`的值是上一次调用[Iterator.moveNext]时设置的。
 * 经测试，在修改集合后`break`，并不会引起异常，但并*不建议*这么做。
 * 下面是重现异常的代码：
 *     main() {
 *       List<int> list = [0, 1, 2];
 *       for(int i in list) {
 *         if(i == 0) {
 *           //for-in后台使用迭代器遍历对象
 *           //在迭代过程中修改集合，会在下一次调用 Iterator.moveNext 时出现异常
 *           list.remove(i);
 *           //break;
 *         }
 *       }
 *
 *       print(list);
 *     }
 *
 * 一些可迭代对象会在每次迭代时，动态计算它们的元素，
 * 如[Iterable.generate]和`sync*`异步函数生成器。
 * 如果计算不依赖其它可能会改变的对象，那么每次迭代时生成的序列应该是一样的。
 *
 * `Iterable`的成员，除了`iterator`自身，都通过查看可迭代对象的元素来工作。
 * 这可以通过获取[iterator]来实现，但一些类可能类可能有更高效的查找结果的方法
 * （如[List]的[last]或[length]，[Set]的[contains]）。
 *
 * 返回`Iterable`的方法（如[map]和[where]）都是
 * [惰性](http://baike.baidu.com/view/2300535.htm)的。
 * 它们会在每次返回的可迭代对象被使用时，才开始迭代（在必要时）原始数据，而不是之前。
 *
 * 因为可迭代对象可能被迭代多次，所以并不建议在迭代器中有任何副作用。
 * 对于类似[map]和[while]的方法，返回的可迭代对象会对每个迭代执行带参函数，
 * 因此那些函数也不应该有副作用。
 */
abstract class Iterable<E> {
  const Iterable();

  /**
   * 创建一个`Iterable`，通过序列来动态生成元素。
   *
   * 生成的可迭代对象有[count]个元素，索引`n`从`0`开始递增，
   * 对应位置的元素是调用`generator(n)`来计算的。
   * 所有的值并没有被缓存，所以每次迭代都是重新计算值。
   *
   * 如果[generator]参数未设置，默认`generator`为整数的恒等函数`(int x) => x`。
   *
   * //TODO
   * If [generator] is omitted, it defaults to an identity function
   * on integers `(int x) => x`, so it may only be omitted if the type
   * parameter allows integer values. That is, if [E] is one of
   * `int`, `num`, `Object` or `dynamic`.
   *
   * 对于`Iterable`，表达式`new Iterable.generate(n, generator))`等同于
   * `const [0, ..., n - 1].map(generator)`。
   */
  factory Iterable.generate(int count, [E generator(int index)]) {
    if (count <= 0) return new EmptyIterable<E>();
    return new _GeneratorIterable<E>(count, generator);
  }

  /**
   * 创建空的可迭代对象。
   *
   * 空的可迭代对象没有元素，迭代的时候它总是立即停止。
   */
  const factory Iterable.empty() = EmptyIterable<E>;

  /**
   * 返回`Iterator`，被允许迭代`Iterable`的所有元素。
   *
   * Iterable可能会指定元素迭代的顺序（如[List]总是按索引来迭代），
   * 也可能不指定（如基于Hash的[Set]可能以任何顺序进行迭代）。
   *
   * 每次读`iterator`，它会返回一个新的迭代器，可用作再次迭代所有元素。
   * 相同Iterable的多个迭代器之间互不影响，但应该以相同顺序返回相同的元素，保持一致性。
   * 如果基础集合没被修改的话。
   *
   * 修改集合可能导致新的迭代器产生不同的元素，也可能改变现有元素的顺序。
   * [List]严格指定了它迭代的顺序，所有修改List可以预测迭代顺序的变化。
   * 基于Hash的[Set]在添加一个新的元素时，可能会完全改变它迭代的顺序。
   *
   * 在创建迭代器之后修改基础集合，在下次调用那个迭代器的[Iterator.moveNext]方法时，
   * 可能产生一个Error。
   * 任何*可更改的*可迭代对象应该指定哪些操作会破坏迭代。
   */
  Iterator<E> get iterator;

  /**
   * 按迭代顺序，对`Iterable`的每个元素调用`f`，用返回值创建一个新的惰性[Iterable]。
   *
   * 这个方法返回一个元素映射的视图。
   * 如果返回的[Iterable]未迭代，设置的[f]函数则不会被调用。
   * 转换之后的元素并不会被缓存。
   * 对同一个元素，迭代多次返回的[Iterable]可能会调用[f]函数多次。
   *
   * 对于不需要的元素，返回的Iterable的方法不会对那些元素调用`f`。
   * 例如，[elementAt]可能仅调用`f`一次。
   */
  Iterable/*<T>*/ map/*<T>*/(/*=T*/ f(E e)) =>
      new MappedIterable<E, dynamic/*=T*/>(this, f);

  /**
   * 使用所有满足测试的元素，创建一个新的惰性[Iterable]。
   *
   * 对于返回的可迭代对象，匹配元素在[iterator]中的顺序和之前一样。
   *
   * 这个方法返回一个元素映射的视图。
   * 如果返回的[Iterable]未迭代，设置的[test]函数则不会被调用。
   * 迭代不会缓存结果。因此，对同一个元素，
   * 迭代多次返回的[Iterable]可能会调用[test]函数多次。
   */
  Iterable<E> where(bool test(E element)) => new WhereIterable<E>(this, test);

  /**
   * 将[Iterable]的每个元素扩展为0个或多个元素。
   *
   * 以对每个元素调用[f]函数后生成的元素，按迭代的顺序，返回新的[Iterable]。
   *
   * 返回的[Iterable]是惰性的，在每次迭代时，才对每个元素调用`f`。
   *
   * 例子：
   *
   *     var pairs = [[1, 2], [3, 4]];
   *     var flattened = pairs.expand((pair) => pair).toList();
   *     print(flattened); // => [1, 2, 3, 4];
   *
   *     var input = [1, 2, 3];
   *     var duplicated = input.expand((i) => [i, i]).toList();
   *     print(duplicated); // => [1, 1, 2, 2, 3, 3]
   *
   */
  Iterable/*<T>*/ expand/*<T>*/(Iterable/*<T>*/ f(E element)) =>
      new ExpandIterable<E, dynamic/*=T*/>(this, f);

  /**
   * 返回true，如果集合中包含一个元素等于[element]。
   *
   * 这个操作会按顺序检查每个元素是否等于[element]，除非有其他高效的方法。
   *
   * 决定[element]和可迭代对象的元素是否相等，默认使用元素的[Object.operator==]方法。
   *
   * 部分可迭代对象的类型可能使用不同的等式。
   * 例如，在使用`contains`时，[Set]可能会有一个自定义等式（参加[Set.identical]）。
   * 并且，调用[Map.keys]返回`Iterable`时，使用的等式应该与`Map`应用于keys的等式相同。
   */
  bool contains(Object element) {
    for (E e in this) {
      if (e == element) return true;
    }
    return false;
  }

  /**
   * 对集合的每个元素，按迭代顺序应用[f]函数。
   */
  void forEach(void f(E element)) {
    for (E element in this) f(element);
  }

  /**
   * 通过迭代，用提供的函数结合（`combine`）集合的所有元素，将集合换算成单一的值，
   *
   * 可迭代对象至少要有一个元素。
   * 如果它只有一个元素，则元素直接返回。
   *
   * 否则，方法会从iterator的第一个元素开始，将它与剩下的元素按迭代顺序结合。
   * 就像：
   *
   *     E value = iterable.first;
   *     iterable.skip(1).forEach((element) {
   *       value = combine(value, element);
   *     });
   *     return value;
   *
   * 下面是一个例子，用于计算可迭代对象所有元素的总和：
   *
   *     iterable.reduce((value, element) => value + element);
   *
   */
  E reduce(E combine(E value, E element)) {
    Iterator<E> iterator = this.iterator;
    if (!iterator.moveNext()) {
      throw IterableElementError.noElement();
    }
    E value = iterator.current;
    while (iterator.moveNext()) {
      value = combine(value, iterator.current);
    }
    return value;
  }

  /**
   * 通过迭代，将集合的所有元素与一个存在的值（`initialValue`）用提供的函数结合（`combine`），
   * 将集合换算成单一的值，
   *
   * 使用[initialValue]作为初始值。
   * 然后迭代元素，用[combine]函数应用每个元素，然后更新之前的值。
   * 如：
   *
   *     var value = initialValue;
   *     for (E element in this) {
   *       value = combine(value, element);
   *     }
   *     return value;
   *
   * 下面是一个例子，用于计算可迭代对象所有元素的总和：
   *
   *     iterable.fold(0, (prev, element) => prev + element);
   *
   */
  dynamic/*=T*/ fold/*<T>*/(var/*=T*/ initialValue,
               dynamic/*=T*/ combine(var/*=T*/ previousValue, E element)) {
    var value = initialValue;
    for (E element in this) value = combine(value, element);
    return value;
  }

  /**
   * 检查可迭代对象的每一个元素是否都满足[test]。
   *
   * 检查按迭代顺序，如果元素中任何一个使[test]返回`false`，该方法返回`false`。
   * 否则返回`true`。
   */
  bool every(bool f(E element)) {
    for (E element in this) {
      if (!f(element)) return false;
    }
    return true;
  }

  /**
   * 将每个元素转换成[String]并连接。
   *
   * 迭代所有元素，通过调用[Object.toString]，将每个元素转换成[String]，
   * 然后用[separator]作分隔符连接字符串。
   */
  String join([String separator = ""]) {
    Iterator<E> iterator = this.iterator;
    if (!iterator.moveNext()) return "";
    StringBuffer buffer = new StringBuffer();
    if (separator == null || separator == "") {
      do {
        buffer.write("${iterator.current}");
      } while (iterator.moveNext());
    } else {
      buffer.write("${iterator.current}");
      while (iterator.moveNext()) {
        buffer.write(separator);
        buffer.write("${iterator.current}");
      }
    }
    return buffer.toString();
  }

  /**
   * 检查可迭代对象是否有任何一个元素满足[test]。
   *
   * 按迭代顺序检查每一个元素，如果元素中任何一个使[test]返回`true`，该方法返回`true`。
   * 否则返回`false`。
   */
  bool any(bool f(E element)) {
    for (E element in this) {
      if (f(element)) return true;
    }
    return false;
  }

  /**
   * 创建一个包含[Iterable]所有元素的[List]。
   *
   * 元素是按迭代顺序排列的。
   * 如果[growable]为`false`，那么List是固定长度的。
   */
  List<E> toList({bool growable: true}) {
    return new List<E>.from(this, growable: growable);
  }

  /**
   * 创建一个与[Iterable]有相同元素的[Set]。
   *
   * 如果可迭代对象包含一个对象多次，或者它包含了一个或多个相等的元素，
   * Set的元素数量可能小于可迭代对象。
   * 元素在Set中的顺序，并不保证和可迭代对象中的顺序相同。
   */
  Set<E> toSet() => new Set<E>.from(this);

  /**
   * 返回[this]对象中元素的数量。
   *
   * 计算所有的元素涉及到迭代所有对象，因此可能很慢。
   * 一些可迭代对象有更高效的方法来查找元素的个数。
   */
  int get length {
    assert(this is! EfficientLength);
    int count = 0;
    Iterator it = iterator;
    while (it.moveNext()) {
      count++;
    }
    return count;
  }

  /**
   * 如果`this`没有元素，则返回`true`。
   *
   * 可能通过`iterator.moveNext()`返回`false`的方式，来判断集合为空。
   */
  bool get isEmpty => !iterator.moveNext();

  /**
   * 如果集合中至少有一个元素，返回`true`。
   *
   * 可能通过`iterator.moveNext()`返回`true`的方式，来判断集合不为空。
   */
  bool get isNotEmpty => !isEmpty;

  /**
   * 返回一个惰性的可迭代对象，包含有此对象最初的[count]个元素。
   *
   * 如果`this`包含的元素小于`count`，返回的`Iterable`包含的元素可能小于`count`。
   *
   * 元素通过迭代[iterator]来进行计算，直到[count]个元素被发现为止。
   *
   * [count]不能为负值。
   */
  Iterable<E> take(int count) {
    return new TakeIterable<E>(this, count);
  }

  /**
   * 返回一个惰性的`Iterable`，包含最初的满足[test]的所有元素。
   *
   * 过滤操作是惰性的。返回的Iterable的每个迭代器在`this`的所有元素之上开始迭代。
   *
   * 元素通过迭代[iterator]来进行计算，直到一个元素被发现`test(element)`返回`false`为止。
   * 在那个时候，返回的Iterable停止（`moveNext()`返回`false`）。
   */
  Iterable<E> takeWhile(bool test(E value)) {
    return new TakeWhileIterable<E>(this, test);
  }

  /**
   * 返回一个惰性的可迭代对象，包含此对象_除了_最初的[count]个元素外的所有元素。
   *
   * 在返回的对象进行迭代操作时，它开始在`this`上迭代，首先跳过开始的[count]个元素。
   * 如果`this`包含的元素小于`count`，返回的`Iterable`为空。
   * 否则，剩下的元素以和`this`相同的迭代顺序开始迭代。
   *
   * 一些可迭代对象也许能够不经过迭代，直接查找后面的元素。如迭代[List]时。
   * 这样的可迭代对象允许忽略最初跳过的元素。
   *
   * [count]不能为负值。
   */
  Iterable<E> skip(int count) {
    return new SkipIterable<E>(this, count);
  }

  /**
   * _跳过_最初的满足测试条件[test]的元素，返回`Iterable`。
   *
   * 过滤操作是惰性的。返回的Iterable的每个迭代器在`this`的所有元素之上开始迭代，
   * 但是跳过所有开始的`test(element)`返回`true`的元素。
   * 如果所有的元素都满足`test`，那么返回的`Iterable`为空。
   * 否则，剩下的元素以和`this`相同的迭代顺序，
   * 以第一个`test(element)`返回`false`的元素开始迭代。
   */
  Iterable<E> skipWhile(bool test(E value)) {
    return new SkipWhileIterable<E>(this, test);
  }

  /**
   * 返回第一个元素。
   *
   * 如果`this`为空，抛出[StateError]错误。
   * 否则返回迭代顺序中的第一个元素。等同于`this.elementAt(0)`。
   */
  E get first {
    Iterator<E> it = iterator;
    if (!it.moveNext()) {
      throw IterableElementError.noElement();
    }
    return it.current;
  }

  /**
   * 返回最后一个元素。
   *
   * 如果`this`为空，抛出[StateError]错误。
   * 否则，*可能*会迭代所有的元素，并返回最后一个。
   * 一些可迭代对象可能有更高效的方法来查找最后一个元素
   * （例如，List能直接访问最后一个元素，而不需要迭代之前的元素）。
   */
  E get last {
    Iterator<E> it = iterator;
    if (!it.moveNext()) {
      throw IterableElementError.noElement();
    }
    E result;
    do {
      result = it.current;
    } while (it.moveNext());
    return result;
  }

  /**
   * 检查可迭代对象仅有一个元素，并返回那个元素。
   *
   * 如果`this`为空或有不止一个元素，抛出[StateError]。
   */
  E get single {
    Iterator<E> it = iterator;
    if (!it.moveNext()) throw IterableElementError.noElement();
    E result = it.current;
    if (it.moveNext()) throw IterableElementError.tooMany();
    return result;
  }

  /**
   * 返回满足[test]断言的第一个元素。
   *
   * 迭代所有元素，并返回第一个满足[test]的元素。
   *
   * 如果没有元素满足[test]，会调用[orElse]函数并返回结果。
   * 如果[orElse]未设置，它默认抛出[StateError]。
   */
  E firstWhere(bool test(E element), {E orElse()}) {
    for (E element in this) {
      if (test(element)) return element;
    }
    if (orElse != null) return orElse();
    throw IterableElementError.noElement();
  }

  /**
   * 返回满足[test]断言的最后一个元素。
   *
   * 一个可以直接访问元素的对象，可能以任何顺序检查元素
   * （例如，List首先检查最后一个元素，然后向List的开始移动）。
   * 默认实现是以迭代顺序迭代元素，对每个元素检查`test(element)`，
   * 最终返回匹配到的最后一个元素。
   *
   * 如果没有元素满足[test]，会调用[orElse]函数并返回结果。
   * 如果[orElse]未设置，它默认抛出[StateError]。
   */
  E lastWhere(bool test(E element), {E orElse()}) {
    E result = null;
    bool foundMatching = false;
    for (E element in this) {
      if (test(element)) {
        result = element;
        foundMatching = true;
      }
    }
    if (foundMatching) return result;
    if (orElse != null) return orElse();
    throw IterableElementError.noElement();
  }

  /**
   * 返回满足[test]的单个元素。
   *
   * 检查所有元素，看看`test(element)`是否返回true。
   * 如果仅有一个元素满足[test]，返回那个元素。
   * 否则，如果没有匹配到元素，或匹配到多个元素，抛出[StateError]。
   */
  E singleWhere(bool test(E element)) {
    E result = null;
    bool foundMatching = false;
    for (E element in this) {
      if (test(element)) {
        if (foundMatching) {
          throw IterableElementError.tooMany();
        }
        result = element;
        foundMatching = true;
      }
    }
    if (foundMatching) return result;
    throw IterableElementError.noElement();
  }

  /**
   * 通过索引返回元素。
   *
   * [index]不能为负值，并且小于[length]。index为0，表示第一个元素
   * （因此`iterable.elementAt(0)`等同于`iterable.first`）。
   *
   * 可能按迭代顺序从开始跳过`index`个元素，返回下一个。
   * 一些可迭代对象可能有更高效的方法来查找元素。
   */
  E elementAt(int index) {
    if (index is! int) throw new ArgumentError.notNull("index");
    RangeError.checkNotNegative(index, "index");
    int elementIndex = 0;
    for (E element in this) {
      if (index == elementIndex) return element;
      elementIndex++;
    }
    throw new RangeError.index(index, this, "index", null, elementIndex);
  }

  /**
   * 返回一个字符串，表示`this`的所有（或部分）元素。
   *
   * 所有元素会调用它们自身`toString`来进行串联。
   *
   * 默认总是包含前三个元素。
   * 如果可迭代对象少于100个元素，它还会包含最后两个元素。
   *
   * 如果串联的字符串不超过80个字符，会包含可迭代对象更多的前面的元素。
   *
   * 转换过程可能会省略调用一些元素的`toString`方法，如果它们被判断不会出现在输出中的话。
   * 并且，在超过100个元素后，迭代会停止。
   */
  String toString() => IterableBase.iterableToShortString(this, '(', ')');
}

typedef E _Generator<E>(int index);

class _GeneratorIterable<E> extends ListIterable<E> {
  /// The length of the generated iterable.
  final int length;

  /// The function mapping indices to values.
  final _Generator<E> _generator;

  /// Creates the generated iterable.
  ///
  /// If [generator] is `null`, it is checked that `int` is assignable to [E].
  _GeneratorIterable(this.length, E generator(int index))
      : // The `as` below is used as check to make sure that `int` is assignable
        // to [E].
        _generator = (generator != null) ? generator : _id as _Generator<E>;

  E elementAt(int index) {
    RangeError.checkValidIndex(index, this);
    return _generator(index);
  }

  /// Helper function used as default _generator function.
  static int _id(int n) => n;
}

/**
 * 允许向前和向后移动的迭代器。
 */
abstract class BidirectionalIterator<E> implements Iterator<E> {
  /**
   * 回移到前一个元素。
   *
   * 如果成功，返回true，并更新[current]。
   * 如果前面没有元素，返回false，并设置[current]为null。
   * Returns true and updates [current] if successful. Returns false
   * and sets [current] to null if there is no previous element.
   */
  bool movePrevious();
}
